The present invention relates to a translation lookaside buffer (TLB) that may be used in a microprocessor to speed up the translation of virtual memory addresses into physical memory addresses. More specifically, the present invention relates to a TLB that contains storage locations that are both hardware-managed and software-managed.
Memory in a computer is a linear array of bytes. Each byte has a unique address known as its physical address. However, many microprocessors do not typically address memory by the memory's physical address. Instead, memory is addressed using virtual memory addresses. A virtual memory address, which is commonly known as a virtual address, is an address of a location in virtual memory.
1.1 Virtual memory
Virtual memory addressing is a technique used to provide the illusion of having a memory space that is much larger than the physical memory available in a computer system. This illusion allows a computer program to be written without regard to the exact size of physical memory. One benefit of virtual memory addressing is that a computer program can easily run on a computer with a wide range of memory configurations and with radically different physical memory sizes. Another benefit is that a computer program may be written that uses a virtual memory size that is much larger than the physical memory available on a particular computer system.
Virtual memory may be thought of as a collection of blocks. These blocks are often of fixed size and aligned, in which case they are known as pages. A virtual address may often be broken down into two parts, a virtual page number and an offset. The virtual page number specifies the virtual page to be accessed. The offset indicates the number of memory bytes from the first memory byte in the virtual page to the addressed memory byte. Physical addresses, which represent where data actually resides in physical memory, may also be broken down into two parts, a physical page number and an offset. The physical page number specifies the physical page to be accessed. The offset indicates the number of memory bytes from the first memory byte in the physical page to the addressed memory byte.
A virtual address must be mapped into a physical address before physical memory may be accessed. The mapping is often maintained through a table, known as a page table. The page table contains virtual to physical memory translations. A virtual to physical memory translation consists of a virtual page number and a corresponding physical page number. Because virtual addresses are typically mapped to physical addresses at the level of pages, the page table may be indexed by virtual page numbers. In addition to virtual to physical memory translations, the page table may often contain other information such as the disk locations where pages are stored when not present in main memory and an indication of whether pages are present in memory or residing on a disk. Typically, the operating system inserts and deletes the virtual to physical memory translations that are stored in the page table. In other words, the page table is managed by the operating system.
1.2 Translation lookaside buffers
Virtual memory requires two memory accesses to fetch a single entry from memory. The first access is into the page table. This access is used to map the virtual address into the physical address. After the physical address is known, then a second access is required to fetch the data. In an effort to speed up memory accesses, conventional microprocessors use a special-purpose cache memory to store certain virtual to physical memory translations. This special-purpose cache memory is often called a translation lookaside buffer (TLB). The number of virtual to physical memory translations in a TLB is typically smaller than the total number of translations in the page table.
Conventional TLBs are often associative. An associative memory is a memory in which the storage locations are identified by a part of or by all of their contents. An associative memory may be contrasted with non-associative memories which identify storage locations by their addresses. A storage location may be a general-purpose microprocessor register or a special-purpose microprocessor register. In addition, a storage location may be a series of memory cells in a cache memory that is internal to or external to a microprocessor. Associative memories are also known as content-addressable memories or CAMs. An associative memory enables faster interrogation and retrieval of a particular data element. Thus, a TLB often returns a requested virtual to physical memory translation in a sufficiently short time so that the two memory accesses required to fetch a single entry from memory occur in a single microprocessor clock cycle.
When a microprocessor addresses memory through a TLB, the virtual page number that is included in the virtual address is used to interrogate the TLB. If the virtual page number is stored in the TLB, then the TLB outputs the physical page number that maps to the virtual page number. Sometimes the TLB does not contain the virtual page number. This is known as a TLB miss. When a TLB miss occurs, the microprocessor often requests the operating system to supply the physical page number from the page table. After the operating system supplies the physical page number, the physical memory is addressed. The delay that occurs when the operating system supplies the physical page number is significant. In fact, it is often possible for a microprocessor to execute many instructions in the time that it takes for the operating system to supply a single physical page number. Thus, microprocessor designers attempt to minimize the frequency of TLB misses.
1.2.1 Hardware-managed translation lookaside buffers
One method used by designers to minimize TLB misses involves the use of a hardware-managed TLB. A hardware-managed TLB contains hardware-managed storage locations. When a TLB miss occurs, the microprocessor references the page table to obtain the missing virtual to physical memory translation. Next, this virtual to physical memory translation is inserted into the hardware-managed storage location.
Thus, a hardware-managed storage location stores virtual to physical memory translations that are inserted into that storage location directly by a microprocessor. In other words, the virtual to physical memory translation is inserted into the storage location by the microprocessor without a "special computer program instruction" that instructs the microprocessor to insert the translation into the particular storage location. An example of a hardware-managed TLB is found in Intel's Pentium.TM. Processor.
A hardware-managed TLB may automatically fill the TLB with a requested physical page number when a TLB miss occurs. This hardware assist may occur concurrently with other microprocessor functions. Further, a hardware-managed TLB may ensure that the most recently used physical pages are stored in the TLB.
The primary disadvantage of hardware-managed TLBs is that the storage of the most recently used page numbers may not be optimal for certain computer programs. Thus, certain computer programs may require significantly more execution time than would be required if the TLB was more optimally managed.
1.2.2 Software-managed translation lookaside buffers
Another method used by designers to minimize TLB misses is the use of a software-managed TLB. A software-managed TLB contains software-managed storage locations. A software-managed storage location stores a virtual to physical memory translation that is inserted into the storage location by a computer program running on a microprocessor. Typically, one or more "special computer program instructions" are used to store a virtual to physical memory translation in a software-managed storage location. Such "special computer program instructions" specify the virtual to physical memory translation that is to be stored. Further, such "special computer program instructions" may optionally specify the particular storage location in which the virtual to physical memory translation is to be stored. Microprocessors will not invalidate or replace a virtual to physical memory translation that is stored in a software-managed storage location.
Thus, a software-managed TLB may be controlled by a computer program running on a microprocessor such as a computer operating system. A computer program may store certain virtual to physical memory translations in the TLB regardless of physical page use patterns. For example, virtual to physical memory translations for operating system kernels, framebuffers, or input-output areas may be stored in the TLB regardless of their use patterns. A virtual to physical memory translation that remains stored in the TLB regardless of the physical page use pattern is known as "locked down" or "pinned" in the TLB. An example of a software-managed TLB is found in the MIPS processor.
A disadvantage of software-managed TLBs is that they may not be automatically filled by microprocessor hardware concurrent with other microprocessor activity. Another disadvantage of software-managed TLBs is that they are less flexible than hardware-managed TLBs. For example, computer programs may not take advantage of additional TLB resources that are included in certain high-performance microprocessors. Similarly, microprocessor manufacturers may be required to build software-managed TLBs that are backwardly compatible with previous non-optimal software-managed TLBs.
1.2.3 Hardware-managed translation lookaside buffers combined with software-managed translation lookaside buffers
Some recent microprocessor designers have included a hardware-managed TLB and a software-managed TLB in a single microprocessor. For example, the PA.sub.-- RISC and the Motorola 88K include both hardware-managed TLBs and software-managed TLBs. While such TLBs provide many of the benefits of the hardware-managed TLBs and software-managed TLBs discussed above, they are not optimal.
First, microprocessor designers must allocate silicon area on the microprocessor for each TLB structure. If either TLB structure is under-utilized, then that silicon area does not contribute to the overall TLB performance. For example, if only a portion of the software-managed TLB is utilized, then the remaining storage locations in the software-managed TLB are unused. Thus, silicon area is wasted.
Second, when a virtual to physical translation is needed, each TLB structure must be looked up in parallel and then the correct translation selected from the correct structure. The selection of a virtual to physical memory translation from the correct TLB and muxing the array outputs typically represent a critical timing path. Thus, a TLB may not return a requested virtual to physical memory translation in a sufficiently short time so that the two memory accesses required to fetch a single entry from memory may occur in a single microprocessor clock cycle.
There is a need for a TLB that optimizes silicon area, does not induce delays in critical paths, and that has the benefits but not the disadvantages of both software-managed TLBs and hardware-managed TLBs.